# -*- coding:utf-8 -*-
# !/usr/bin python3

# Import exceptions.Empty class
import sys

sys.path.append("../exceptions")
from empty import Empty

"""用单向链表实现栈"""


class LinkedStack:
    """通过单链表存储的方式实现先进后出的栈"""

    class _Node:
        """不共有类：用于存储单个链表结点"""

        __slot__ = "_element", "_next"

        def __init__(self, element, next_node):
            self._element = element
            self._next = next_node

    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, e):
        self._head = self._Node(e, self._head)
        self._size += 1

    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty!")
        return self._head._element

    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty!")
        ret = self._head._element
        self._head = self._head._next
        self._size -= 1
        return ret


if __name__ == "__main__":
    s = LinkedStack()
    s.push("a")
    s.push(1)
    s.push(3)
    print(s.pop())
    print(s.pop())
    print(s.pop())
